/*
 * https://leetcode-cn.com/problems/permutations/
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
void back_track(int* nums, int numsSize, int first, int **ret, int *cnt)
{
    if (first == numsSize) {
        ret[*cnt] = (int *)malloc(sizeof(int) * numsSize);
        memcpy(ret[*cnt], nums, sizeof(int) * numsSize);
        (*cnt) += 1;
        return;
    }
    for (int i = first; i < numsSize; i++) {
        swap(&nums[i], &nums[first]);
        back_track(nums, numsSize, first + 1, ret, cnt);
        swap(&nums[i], &nums[first]);
    }
}

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    int cnt = 0;
    int **ret = (int **)malloc(sizeof(int *) * 720);

    back_track(nums, numsSize, 0, ret, &cnt);

    *returnColumnSizes = (int *)malloc(sizeof(int) * cnt);
    for (int i = 0; i < cnt; i++) (*returnColumnSizes)[i] = numsSize;
    *returnSize = cnt;
    return ret;
}